package com.itheima.leetcode.od.b.dynamicprogramming.slidingwindow;

import java.util.HashMap;
import java.util.Map;

/**
 * (B卷,100分)- 恢复数字序列（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 对于一个连续正整数组成的序列，可以将其拼接成一个字符串，再将字符串里的部分字符打乱顺序。如序列8 9 10 11 12，拼接成的字符串为89101112，打乱一部分字符后得到90811211，原来的正整数10就被拆成了0和1。
 * <p>
 * 现给定一个按如上规则得到的打乱字符的字符串，请将其还原成连续正整数序列，并输出序列中最小的数字。
 * <p>
 * 输入描述
 * <p>
 * 输入一行，为打乱字符的字符串和正整数序列的长度，两者间用空格分隔，字符串长度不超过200，正整数不超过1000，保证输入可以还原成唯一序列。
 * <p>
 * 输出描述
 * <p>
 * 输出一个数字，为序列中最小的数字。
 * <p>
 * 用例
 * <p>
 * 输入	19801211 5
 * 输出	8
 * 说明	无
 * <p>
 * 题目解析
 * <p>
 * 本题“打乱字符的字符串”的是由“连续正整数序列”组成的，而题目又说：正整数不超过1000
 * <p>
 * 因此，本题可以考虑使用滑动窗口，在1~1000整数范围内滑动，滑窗窗口的长度为输入的“连续正整数序列”的长度。
 * <p>
 * 我们只需要统计“打乱字符的字符串”中各字符的数量，以及滑窗中各字符的数量，如果所有字符对于的数量都相同，那么说明对应滑窗就是一个符合要求的连续正整数数列，我们只需要取滑窗第一个数值即可。
 * <p>
 * 滑窗在运动过程中，可以利用差异比较，即当前滑窗相交于上一个滑窗，失去了一个数字，新增了一个数字，当前滑窗只需要针对失去数字和新增数字的字符做数量修改即可。
 */
public class RestoreNumericalSequence {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        String s = sc.next(); // 打乱字符的字符串
        int k = sc.nextInt(); // 连续正整数序列的长度*/

        String s = "19801211"; // 打乱字符的字符串
        int k = 5; // 连续正整数序列的长度

        System.out.println(getResult(s, k));
    }

    /**
     * 滑动窗口(暴力枚举)
     *
     * @param s
     * @param k
     * @return
     */
    public static int getResult(String s, int k) {
        // 统计输入字符串中各个字符的频率
        Map<Character, Integer> targetFreq = new HashMap<>();
        for (char c : s.toCharArray()) {
            targetFreq.put(c, targetFreq.getOrDefault(c, 0) + 1);
        }

        // 限制搜索范围
        int maxSearch = 1000 - k + 1;
        for (int start = 1; start <= maxSearch; start++) {
            // 统计当前窗口中的字符频率
            Map<Character, Integer> windowFreq = new HashMap<>();
            for (int i = 0; i < k; i++) {
                String numStr = String.valueOf(start + i);
                for (char c : numStr.toCharArray()) {
                    windowFreq.put(c, windowFreq.getOrDefault(c, 0) + 1);
                }
            }

            // 比较字符频率
            boolean isMatch = true;
            for (Map.Entry<Character, Integer> entry : targetFreq.entrySet()) {
                char c = entry.getKey();
                int freq = entry.getValue();
                if (!windowFreq.containsKey(c) || !windowFreq.get(c).equals(freq)) {
                    isMatch = false;
                    break;
                }
            }

            if (isMatch && windowFreq.size() == targetFreq.size()) {
                return start;
            }
        }

        return -1;
    }
}